package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * @author Administrator
 * @date 2019/8/30 10:55
 */
public class UniquePaths {
    /**
     * * 有一个机器人的位于一个 m × n 个网格左上角。
     * * 机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。
     * * 问有多少条不同的路径？
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    f[i][j] = 1;
                } else {
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }
        return f[m - 1][n - 1];
    }

    /**
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     */
    @Test
    public void uniquePathsWithObstacles() {
        Assert.assertEquals(0, uniquePathsWithObstacles(new int[][]{{1, 0}}));
        Assert.assertEquals(2, uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}));
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    f[i][j] = 0;
                } else if (i == 0 && j == 0) {
                    f[i][j] = 1;
                } else if (i == 0) {
                    f[i][j] = f[i][j - 1];
                } else if (j == 0) {
                    f[i][j] = f[i - 1][j];
                } else {
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }
        return f[m - 1][n - 1];
    }

    /**
     * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     */
    @Test
    public void minPathSum() {
        Assert.assertEquals(7, uniquePathsWithObstacles(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
    }

    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    f[i][j] = grid[i][j];
                } else if (i == 0) {
                    f[i][j] = f[i][j - 1] + grid[i][j];
                } else if (j == 0) {
                    f[i][j] = f[i - 1][j] + grid[i][j];
                } else {
                    f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
                }
            }
        }
        return f[m - 1][n - 1];
    }

    /**
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     * <p>
     * 例如，给定三角形：
     * <p>
     * [
     * [2],
     * [3,4],
     * [6,5,7],
     * [4,1,8,3]
     * ]
     * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     */
    @Test
    public void minimumTotal() {
        List<List<Integer>> triangle = Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4), Arrays.asList(6, 5, 7), Arrays.asList(4, 1, 8, 3));
        Assert.assertEquals(11, minimumTotal(triangle));
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }
        int[] totals = new int[]{triangle.get(0).get(0)};
        // 每层循环
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> line = triangle.get(i);
            if (line == null || line.size() == 0) {
                return 0;
            }
            int[] currentTotals = new int[line.size()];
            // 循环当前层的所有点，并计算到达这些点的最小路径和
            currentTotals[0] = totals[0] + line.get(0);
            currentTotals[currentTotals.length - 1] = totals[totals.length - 1] + line.get(line.size() - 1);
            for (int j = 1; j < line.size() - 1; j++) {
                currentTotals[j] = Math.min(totals[j - 1], totals[j]) + line.get(j);
            }
            totals = currentTotals;
        }
        int min = Integer.MAX_VALUE;
        for (int total : totals) {
            min = Math.min(min, total);
        }
        return min;
    }

}
